import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-20
 * Time:16:46
 */
public class TestBInaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

    }
    public static TreeNode create(){
        TreeNode nodeA=new TreeNode('A');
        TreeNode nodeB=new TreeNode('B');
        TreeNode nodeC=new TreeNode('C');
        TreeNode nodeD=new TreeNode('D');
        TreeNode nodeE=new TreeNode('E');
        TreeNode nodeF=new TreeNode('F');
        TreeNode nodeG=new TreeNode('G');
        TreeNode nodeH=new TreeNode('H');
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        nodeE.right=nodeH;
        return nodeA;
    }
    //是不是高度平衡的树
    public boolean isBalanced(TreeNode root) {
//        if(root==null){
//            return false;
//        }
//        //判断根
//        if(eachDepth(root)>1){
//            return false;
//        }
//        //判断左
//        if(eachDepth(root.left)<1){
//            return isBalanced(root.left);
//        }
//        //判断右
//        if(eachDepth(root.right)<1){
//            return isBalanced(root.right);
//        }
//        return true;
        //正确
        if(root==null) {
            return true;
        }
        int ret1=eachDepth(root.left);
        int ret2=eachDepth(root.right);
        if(ret1-ret2<2){
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        return false;
        //正确的答案
//        if(root==null){
//            return true;
//        }
//        //判断根
//
//        int ret1=eachDepth(root.left);
//        int ret2=eachDepth(root.right);
//
//        return Math.abs(ret1-ret2)<2&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public int eachDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int ret1=eachDepth(root.left);
        int ret2=eachDepth(root.right);
        return ret1>ret2?ret1+1:ret2+1;
    }
    //这个函数出问题了
//    public int eachDepth(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        int ret1=eachDepth(root.left);
//        int ret2=eachDepth(root.right);
//        return ret1>ret2?(ret1+1)-(ret2+1):(ret2+1)-(ret1+1);
//    }

    //返回最高的深度
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int ret1=maxDepth(root.left);
        int ret2=maxDepth(root.right);
        return ret1>ret2?ret1+1:ret2+1;
    }
    //判断一颗是不是另一颗的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        //判断现在是不是相同的节点
        if(isSameTree(root,subRoot)){
            return true;
        }
        //判断是不是左边的
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        //判断是不是右边的
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    //判断是不是相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p!=null&&q!=null){
                if(p.val!= q.val){
                    return false;
                }
                boolean l=isSameTree(p.left,q.left);
                boolean r=isSameTree(p.right,q.right);
                return l&&r;
            }
            if(p==null&&q==null){
                return true;
            }
            return false;
    }
//    public static void preOrder(TreeNode A){
//        //先打印遇见的然后在打印左树的最后打印右树
//        System.out.print(A.val+" ");
//        if(A.left!=null){
//            preOrder(A.left);
//        }
//        if(A.right!=null){
//            preOrder(A.right);
//        }
//    }
    public static void preOrder(TreeNode A){
        //先打印遇见的然后在打印左树的最后打印右树
        if(A==null){
            return;
        }
        System.out.print(A.val+" ");
            preOrder(A.left);
            preOrder(A.right);
    }
    //中序遍历
    public static void inOrder(TreeNode A){
        if(A==null){
            return;
        }
        inOrder(A.left);
        System.out.print(A.val+" ");
        inOrder(A.right);
    }
    //后序遍历
    public static void postOrder(TreeNode A){
        if(A==null){
            return;
        }
        postOrder(A.left);
        postOrder(A.right);
        System.out.print(A.val+" ");
    }
    // 获取树中节点的个数
    //public static int ret;
    public static int size(TreeNode root){
        //递归
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    // 获取叶子节点的个数
    public static int getLeafNodeCount(TreeNode root){
        //子问题
//        if(root.left==null&&root.right==null){
//            return 1;
//        }
//        if(root.right==null){
//            return getLeafNodeCount(root.left);
//        }
//        if(root.left==null){
//            return getLeafNodeCount(root.right);
//        }
//        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
        //遍历
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }else {
            return getLeafNodeCount(root.right)+getLeafNodeCount(root.left);
        }
    }
    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    public static int getKLevelNodeCount(TreeNode root,int k){
        //k=1
        //循环k-1次，
        if(root==null||k<=0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度
    public static int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int right=getHeight(root.right);
        int left=getHeight(root.left);
        return (right>left?right:left)+1;
        //返回值导致重复递归，时间复杂度就会变大
        //return (getHeight(root.right)>getHeight(root.left)?getHeight(root.right):getHeight(root.left))+1;
    }
    // 检测值为value的元素是否存在
    public static TreeNode find(TreeNode root, int val) {
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }else {
            TreeNode ret1=find(root.left,val);
            if (ret1 != null) {
                return ret1;
            }
            TreeNode ret2 = find(root.right, val);
            if (ret2 != null) {
                return ret2;
            }
        }
        return null;
    }
    //层序遍历
    public static Queue<TreeNode> queue=new LinkedList<>();
    public static void levelOrder(TreeNode root){
        queue.offer(root);
        while(!queue.isEmpty()){
            System.out.print(queue.peek().val);
            TreeNode cur=queue.peek();
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
            queue.poll();
        }
    }
    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){

        return true;
    }
    public static void main(String[] args) {
        TreeNode A=TestBInaryTree.create();
        TestBInaryTree.preOrder(A);
        System.out.println();
        TestBInaryTree.inOrder(A);
        System.out.println();
        TestBInaryTree.postOrder(A);
        System.out.println();
        System.out.println(TestBInaryTree.size(A));
        System.out.println();
        System.out.println(TestBInaryTree.getLeafNodeCount(A));
        System.out.println(getKLevelNodeCount(A, 4));
        System.out.println(getHeight(A));
        System.out.println(find(A,'H'));
        System.out.println();
        levelOrder(A);
    }
}
